00100	.DEVICE XGP
00200	
00300	.FONT 1 "FIX25"
00400	.FONT 2 "SIGN57"
00500	.FONT 3 "SHD40"
00600	.FONT 4  "BDI25"
00700	.FONT 5  "NGR20"
00800	.TURN ON "↓_π{"
00900	.TURN ON "⊗" FOR "%"
01000	.MACRO B ⊂ BEGIN VERBATIM GROUP ⊃
01100	.MACRO E ⊂ APART END ⊃
01200	.TABBREAK
01300	.COMPACT
01400	.SELECT 1
     

00100	.PORTION TITLEPAGE
00200	.EVERY FOOTING(,⊗5{DATE}⊗*,)
00300	.BEGIN CENTER 
00400	.RETAIN
00500	.PAGE FRAME 54 HIGH 91 WIDE
00600	.EVENLEFTBORDER←ODDLEFTBORDER←1000;
00700	.FONT 6 "SGN114"
00800	⊗6   BEINGS:⊗*
00900	
01000	⊗2REPRESENTATION OF KNOWLEDGE
01100	AS INTERACTING MODULES
01200	⊗*
01300	
01400	⊗4Applied to Automatic Program Synthesis⊗*
01500	.END
01600	.GROUP SKIP 10
01700	Fourth Draft:  NOT FOR DISTRIBUTION
01800	.GROUP SKIP 10
01900	⊗3DOUG LENAT 
02000	
02100	STANFORD UNIVERSITY
02200	
02300	ARTIFICIAL INTELLIGENCE LABORATORY⊗*
02400	
02500	.PORTION CONTENTS
02600	.GROUP SKIP 10
02700	⊗2TABLE OF CONTENTS⊗*
02800	.GROUP SKIP 10
02900	.SELECT 1
03000	.B
03100	    1.	Abstract  . . . . . . . . . . . . . . . .  1
03200	    2.	Introduction  . . . . . . . . . . . . . .  2
03300	    3.	Theory:   Ideas . . . . . . . . . . . . .  3
03400	    4.	Reality:  Examples  . . . . . . . . . . . 10
03500	    5.	Theory:   Design. . . . . . . . . . . . . 15
03600	    6.	Reality:  Examples  . . . . . . . . . . . 19
03700	    7.	Reality:  Results . . . . . . . . . . . . 23
03800	    8.	Theory:   Conclusions . . . . . . . . . . 28
03900	    9.	Acknowledgements  . . . . . . . . . . . . 32
04000		Appendix 1: BEING parts . . . . . . . . . A1.1
04100		Appendix 2: the BEINGs  . . . . . . . . . A2.1
04200		Appendix 3: BEING usage . . . . . . . . . A3.1
04300		Appendix 4: CF  program . . . . . . . . . A4.1
04400		Appendix 5: the dialogue creating CF  . . A5.1
04500		Appendix 6: trial running of CF . . . . . A6.1
04600		Bibliography  . . . . . . . . . . . . . . BIB.1
04700	.E
04800	.SELECT 1
     

00100	.PORTION ABSTRACT
00200	.PAGE FRAME 54 HIGH 74 WIDE
00300	.EVERY HEADING(⊗3BEINGS⊗*,,⊗4Doug Lenat⊗*)
00400	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {IF PAGE = 1 THEN 1 ELSE PAGE})
00500	.COUNT PAGE PRINTING "1"
00600	.NEXT PAGE
00700	.GROUP SKIP 10
00800	
00900	⊗21. ABSTRACT⊗*
01000	.GROUP SKIP 10
01100	
01200	Knowledge may be organized as  a  community  of  interacting  modules
01300	(e.g.,  ACTORS [Hewitt]), in which control also resides.  By granting
01400	each module a complex structure, yet constraining that that structure
01500	be   standard   over  all  the  modules,  some  new  theoretical  and
01600	experimental results were found.  The domain  of  this  research  was
01700	heuristic  automatic  synthesis of inductive inference LISP programs.
01800	Since these modules, called BEINGs, are the only  entities  permitted
01900	to  exist  theoretically, the generated code must also be a community
02000	of BEINGs.  Like the original pool,  they  must  be  able  to  answer
02100	questions  about  themselves as they run.  An experimental system was
02200	partially implemented.  It  synthesized  a  few  programs  from  very
02300	restricted dialogues.  Some unexpected problems were encountered, and
02400	some aspects which were considered ignorable seem  not  to  be.   The
02500	performance  of  the  system  is discussed, and a preliminary view of
02600	BEINGs assessed.
     

00100	.PORTION THESIS
00200	⊗22. INTRODUCTION⊗*
00300	
00400		This  paper  reports  on a scheme for representing knowledge,
00500	partially  realized  in  an  experimental  system  (PUP6)  aimed   at
00600	generating  LISP  programs  from dialogues with the user. The methods
00700	employed are not formal, but rather involve structuring of  knowledge
00800	about  programming,  about  the  task  domain,  and about transfer of
00900	control.  To date, PUP6 has synthesized three significantly different
01000	target programs:  a concept formation program (similar to [Winston]),
01100	a grammatical inference program, and a simple information storage and
01200	retrieval on keys system  
01300	(referred  to  as, respectively, CF, GI, and INF).
01400	Specification is via rigid,
01500	extended dialogues carried on with the user,  in
01600	a  small  subset  of  English,  in  which  the task is delineated and
01700	questionable details are discussed.  The  specification  is  partial,
01800	and  the system makes assumptions continually. This is what is meant,
01900	in the sequel, by ⊗4Automatic Programming.  Target program⊗* will refer
02000	to code which has been successfully generated by such a system.
02100	This will typically be written in the same language as the system itself.
02200	⊗4Dialogue⊗* is the interactive communication between the user and the
02300	automatic programming system, which results in target code synthesis.
02400		The  CF  target  program  was cleanly specified, an annotated
02500	protocol was done, and the BEINGs needed to reproduce  the  reasoning
02600	present  in  that protocol were fasioned. Additions were made to PUP6
02700	before it could synthesize GI or INF.
02800		The  main  successes  of the experiment were that the desired
02900	reasoning steps in the original protocol
03000	were actually simulated, most of the BEINGs were used
03100	in  writing  more  than one of the programs, and the synthesized code
03200	could be interrupted and asked a few kinds of  questions.   The  main
03300	defects  were  the  inflexibility of the system to new dialogues, the
03400	inability for  the  user  to  add  new,  high-level,  domain-specific
03500	knowledge,  and  the verbosity of the system.  Some of these problems
03600	may arise from the annotated protocol technique employed to  get  the
03700	BEINGs  initially,  and  not  from  anything  inherent  to the BEINGs
03800	representation.
03900		Our  treatment will follow these lines:  First, the ideas are
04000	presented, including a  discussion  of  BEINGs.   Examples  are  then
04100	provided to illustrate these concepts. The next section describes the
04200	implementation, and explains the choice of targets.  Only  then  will
04300	performance  be  evaluated.  From  the experience with PUP6 are drawn
04400	several preliminary conclusions about both the utility of the  BEINGs
04500	representation and about problems relevant to Automatic Programming.
04600		The  appendices  present  further   details,   samples,   and
04700	examples.   First  comes  a  description  of  each BEING part, then a
04800	summary of the knowledge contained in each BEING.  Appendix  3  is  a
04900	table  of data recording how the BEING community interacts. The final
05000	appendices  present  excerpts  from  the  CF   program,   from   PUP6
05100	synthesizing CF, and from CF itself running.
     

00100	.NEXT PAGE
00200	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},THEORY:  IDEAS)
00300	⊗23. THEORY:  IDEAS⊗*
00400		How should knowledge be represented?  Many  researchers  feel
00500	that a simple, uniform formalism should be used for all facts; others
00600	disagree, claiming that complexity of  behavior  both  justifies  and
00700	demands complexity of representation.  The BEINGs concept may resolve
00800	this uniformity vs.  structure controversy; at the  least,  it  is  a
00900	compromise.  One  must  recognize  the  advantages  of each side, and
01000	refuse to give them up. The  benefits  of  the  former  include  easy
01100	addition  of  knowledge  [Newell]  and  simple, aesthetic methods for
01200	combining information [McCarthy]. Structure,  however,  is  necessary
01300	for (⊗4combinatorially⊗*) efficient handling of large amounts of data
01400	[MIT].  PUP6 integrates these two ideas into the concept of BEINGs. A
01500	BEING  is  a  collection  of  about  thirty  little bits of INTERLISP
01600	[Teitelman] code; the answers to thirty questions  about  the  BEING.
01700	That  is,  a  BEING  is  a small, loosely-knit LISP program, which is
01800	considered equivalent to its answers to these fixed questions.  Every
01900	scrap  of knowledge and all control structure should be encoded
02000	into BEINGs. There should be nothing else  in  the  system  but  this
02100	interacting community.
02200		PUP6  embodies  only  some  of  the  ideas  and   constraints
02300	discussed  in  this section.  For example, economy demanded some very
02400	fast auxilliary functions, demons, and pure  data  structures.  These
02500	reduced  the  computation  time  by a constant factor (about ten), by
02600	saving on the overhead implicit in each call to a BEING; they did not
02700	therefore  reduce the ⊗4combinatorial⊗* effort involved. This will be
02800	explained in the REALITY section, along with any other deviations  of
02900	PUP6 from an ideal BEINGs community.
03000		Notice that while  each  BEING  is  highly  structured,  this
03100	structure is standard over the entire pool. Each BEING part is itself
03200	a little BEING, etc.,  and  this  infinite  regress  stops  when  the
03300	contents  of  a BEING part becomes sufficiently primitive. As will be
03400	discussed later, the BEINGs mimic a  human  programmer;  whatever  he
03500	considers  primitive  when  writing  the  program,BEINGs may consider
03600	primitive.  Typically this level is about the same as  the  INTERLISP
03700	[Teitelman]  language:     a primitive is a single INTERLISP function
03800	call, or a  few  simple  ones  connected  trivially.  Each  BEING  is
03900	cognizant  of  the  set  of  thirty  questions,  in the sense that in
04000	answering one of them it may freely ask  questions  of  other  BEINGs
04100	(often  through  nondeterministic  goal  statements.)  A  few  of the
04200	BEING-PARTS might be:     what is your basic idea and  purpose,  what
04300	effects  do  you have, how do you go about causing them, what must be
04400	ensured before you begin, how  complicated  are  you,  what  is  your
04500	chance  of  success, are  you recursive, whom else might you transfer
04600	control to, what alternatives to you exist, what BEINGs are a  little
04700	more/less  general than you are, do you evaluate your arguments, what
04800	is the nature of the value you return, why do you exist, why  do  you
04900	want  to  be  in  control  now, etc. The reader may wish to glance at
05000	Appendix 1, to  see  the  particular  set  of  questions  which  were
05100	actually  settled  upon.   When  he  feels  the  urge  for a concrete
05200	example, he should glance over pages 8-11 and Appendices 4 and 5.
05300		The delineation of this set of questions has much to do with
05400	the epistemology of programming.  The BEING parts may be classified
05500	according to their usage.  Each BEING part has two tasks: it may be
05600	⊗4asked⊗* about something, and it may be ⊗4called⊗* on to do 
05700	something. Each of these may involve asking and calling other parts
05800	of itself and of other BEINGs, but typically the second activity
05900	involves an extra level of evaluation. Some parts are relevant to 
06000	only one of these functions; most are at least oriented more toward
06100	one than the other. For example, the ARGS part may be asked trivial
06200	questions about the arguments to the BEING, but its main role is to
06300	bind the arguments when the BEING is given control. In Appendix 1,
06400	the role of each part is described. The ask-oriented parts divide
06500	into categories based on why they are queried: to decide which BEING
06600	to pass control, to tell whether the BEING has a certain property, or
06700	to give a memorized English answer to the user under proper stimulation
06800	(examples of these three types are: WHEN, PREDICATE, WHAT).
06900		The BEINGs control themselves in a simple way. A very general
07000	BEING, SERVE_THE_USER, has control initially. In general, some  BEING
07100	⊗4B⊗*  will  be  in  control.   Its BEING parts are assembled into an
07200	executable function, and it is run.  During the course of its  reign,
07300	⊗4B⊗*  will  want things done and/or tested which it cannot manage by
07400	itself.  This corresponds to when a normal program needs  to  call  a
07500	subroutine.  What ⊗4B⊗* does is to call on SATISFY by name, supplying
07600	a description of what is wanted.  SATISFY assembles itself, asks  the
07700	entire  BEING  pool  "who can do this thing?", and collects a list of
07800	the reponders.  SATISFY then calls  CHOOSE_FROM  by  name,  supplying
07900	this  list  and  the original request. Each responder is asked why he
08000	should be allowed to go now (the WHEN part) and how costly he will be
08100	if he does go (the COMPLEXITY part.) The best responder BEING is then
08200	passed control. If  he  succeeds  in  his  mission,  SATISFY  returns
08300	control to ⊗4B⊗*. Otherwise the remaining responders are compared and
08400	a new one is tried. If they all fail, then SATISFY tells  ⊗4B⊗*  that
08500	it has failed. ⊗4B⊗* then decides whether to try something else or to
08600	fail itself. In addition to these goal  statements,  there  exists  a
08700	"world" consisting of assertions and variables with values. These are
08800	regarded as trivial cases of BEINGs, possessing only  one  part.   So
08900	⊗4B⊗*  may also query this data base by saying "what assertions match
09000	this one...", or by asking "what is the value of...".  These  actions
09100	can be programmed in a much more efficient manner than as BEINGs.
09200		The CHOOSE_FROM and SATISFY BEINGs act as global schedulers, and
09300	detract from the equality proclaimed earlier for each BEING. This again
09400	touches on the philosophy of programming. Since the parts which reflect
09500	how desirable a BEING is at any given time are standard over all BEINGs,
09600	the mechanism for choosing the control successor will be about the same
09700	whoever is in control. Either this choice algorithm must be duplicated
09800	inside every BEING, or else a universal chooser BEING must be tolerated.
09900	It seems that one must have either duplication of knowledge or else 
10000	factor out the common knowledge into some higher-level interaction
10100	BEINGs.
10200		Theory would indicate that BEINGs must be assembled by  other
10300	BEINGs dynamically. In practice, the way a BEING's parts fit together
10400	is uniform over all the BEINGs at all times. Thus one simple function
10500	(or  assembled BEING) can assemble all the BEINGs initially into LISP
10600	functions.  The precise algorithm for doing this is discussed in  the
10700	next section.
10800		BEINGs are the only  entities  permitted  (theoretically)  to
10900	exist in our system; ergo all our code must be written as BEINGs, and
11000	must be written by BEINGs.
11100		An  obvious but crucial consequence is that ⊗4some⊗* BEING(s)
11200	must write new BEINGs. The significant point is 
11300	that the BEING  who  knows  about
11400	⊗4X⊗*  takes  charge  of  generating  BEINGs  relating to ⊗4X⊗*.  For
11500	example,  the  INSERT  BEING  can  do  inserting  by  one  of  a  few
11600	algorithms,  and  he  can  also  write (by specializing himself) more
11700	specific  insert  routines,  and  he  can  answer   questions   about
11800	inserting. This idea is analogous to any reliance upon experts (e.g.,
11900	[Feigenbaum]), and also reemphasizes the theme of any modular
12000	representation of knowledge.
12100		A second consequence is that the output code  will  have  all
12200	the ⊗4types⊗* of "intelligence" that any BEING community has:      it
12300	can write variations of itself, modify itself according to the user's
12400	complaints,  and  answer questions about what it is doing as it runs.
12500	The specialized code cannot, of course, write the full complement  of
12600	programs the original system could write.
12700		In a similar vein, ⊗4some⊗* BEING(s) must do the  translation
12800	of  the  users' quasi-English inputs into BEING-usable form. ↓_Each_↓
12900	BEING ⊗4X⊗* is charged with recognizing English related to  ⊗4X⊗*.
13000	Thus  translation
13100	consists  of  querying  "who  can  recognize  ..."  and waiting for a
13200	response. For example, our  INSERT  BEING  must  also  recognize  and
13300	process phrases involving inserting, stack-pushing, and merging.
13400		A result of this treatment of natural language
13500	processing is that any phrase which can be translated can be acted
13600	upon, and any phrase which can't be translated probably ⊗4can't⊗*
13700	be acted upon (even if it is rephrased).  Since patterns are used,
13800	if the global structure of the sentence is recognized, then the user
13900	need only be asked to clear up the difficult sub-parts.
14000		Three constraints are present which reflect new biasses  more
14100	than  new  insights:       one need not feel any reverence toward the
14200	exploratory anthropomorphic paradigm of programming 
14300	(ignore details,  catch  them
14400	later by debugging).  As in all programming, 
14500	decisions continually crop up which
14600	the system is not able to resolve  at  the  time. The  BEINGs  system
14700	should  always  spend  a significant effort deferring the decision as
14800	long as possible.  When, at last, no progress can be made without its
14900	resolution,  and  if the system is still unsure, then either the user
15000	settles the question or else a backtrack point is reluctantly set up.
15100	"Reluctant" means that it is the last of several alternatives which
15200	are tried.
15300	But  often,  by  this  time,  some  new  information is present which
15400	enables the system to resolve the decision, thus reducing the  amount
15500	of  backtracking.   If  there  are two or more decisions which can no
15600	longer be deferred, the system tackles first the one estimated to  be
15700	the easiest (analogous to Occam's razor).
15800		The final bit of philosophy is that most of the  carelessness
15900	bugs  can be eliminated through this deferral, feed-forward, and very
16000	precise  record-keeping.  Humans  depend  on  their  adaptability  to
16100	compensate  for limitations in their brain hardware (long write times
16200	for long-term memory and  external  memory,  and  limited  short-term
16300	memory size force us to ignore details; see [Newell]) but there is no
16400	need for an ⊗4automatic⊗* programming system to do so.  For  example,
16500	when  a  list  structure  is  first  encountered,  the system records
16600	warnings that it is undefined, no accesses, insertions, or  deletions
16700	have  been  observed,  and  so  on.  Each such worry is weighted, and
16800	periodically the system resolves such  warning  notes  --  especially
16900	near the completion of the target program.
17000		To understand why Automatic Programming is a good task for a
17100	BEINGs pool, it is necessary to defocus our interest momentarily.
17200	The BEINGs representation may be  suitable  for  simulating  any
17300	complex  task ⊗4T⊗* involving frequent small interventions by various
17400	experts. In addition to writing programs, this activity could  be  as
17500	diverse  as  playing  chess,  running a business, simulating physical
17600	interactions,  and  playing  volleyball.  For  the  latter  task,   a
17700	BEINGs-based system might create a specialized BEING for each player,
17800	perhaps with a complexity vector indicating his abilities,  reflexes,
17900	etc.  The  BEING  in  control would be the player hitting the ball. A
18000	specialized  Choose-from  BEING   would   decide   who   goes   next,
18100	occasionally interpreting a tie between BEINGs vying for control as a
18200	collision on the court.
18300		There  is  one  particular  bias  of  BEINGs  toward  writing
18400	high-level programs, over other activities. The  new  BEINGs  created
18500	during  the  execution of a specified task are kept distinct from the
18600	original set  of  BEINGs.  Then  a  ⊗4program⊗*  for  task  ⊗4T⊗*  is
18700	accomplished  by doing ⊗4T⊗* and then dumping the new BEINGs out onto
18800	a new file.  The entire old  BEINGs  pool  is  then  treated  as  the
18900	language  supporting this file. As a corollary, asking a BEINGs-based
19000	system to write any subset of itself is the null task!
19100		Most  programmers  intentionally augment their code to aid in
19200	later debugging, modification, and readability by humans.  These aids
19300	are  typically  comments,  summaries,  over-generalized  subroutines,
19400	optional print statements,  and  runtime  statistics.  Recently, the
19500	structure  of  the  program  itself has also recognized as a powerful
19600	manipulable element, affecting the accessability of the code, not just
19700	its length or running time.
19800	The length of any program written as a pool  of
19900	BEINGs  is several times as long as a clean hand-coded version.  This
20000	extra code, the parts of each new BEING which are superfluous, may be
20100	viewed as well-organized self-documentation.  They should improve the
20200	debugging, expansion, and  accessibility  (to  alien  users)  of  the
20300	synthesized code.
20400		Some assertions are so meaningful  to  the  user,
20500	that they should be stored in the code itself.  At any time, the user
20600	may look at a piece of code; the comments present  ⊗4then⊗* are  all
20700	assertions pertaining to that piece of code at that time.
20800	BEINGS may use comments at  several  different  levels.  At  the
20900	lowest  level,  each  comment  is  merely  a  unique token; it may be
21000	inserted, removed, or searched  for.   Slightly  better,  the  BEINGs
21100	system can ask "is there a comment involving ...". For this purpose, a
21200	constrained syntax for the comments should be developed. Otherwise
21300	(as, unfortunately in PUP6) each new comment must be attended to
21400	ad hoc.      Still higher level
21500	usage of comments would occur if a BEING looked at a comment  totally
21600	ignorant of it, and TRANSLATEd it into something meaningful. 
21700		When imagining an ideal AP  (automatic  programming)  system,
21800	one  ability  we  might  wish  for  is  that  it  be  able to input a
21900	well-documented program, glean pure programming knowledge from it,
22000	and  transform  this  into  a  format  it  can use.  Also, to improve
22100	itself, it should be capable of digesting a sample, valid AP  dialog,
22200	and (perhaps through additional user interaction) modify itself so it
22300	could actually carry on that  dialog.  
22400	Another ideal to hope for is that the user be permitted to do whatever
22500	he can whenever he can; if he suddenly thinks of a stray caution, the
22600	AP system should accept it (e.g., "Oh, don't forget the zero test").
22700	BEINGs were not designed with
22800	these ideals in mind, and as a result they may be an
22900	insufficient framework for achieving this.
23000	By studying the difficulties of the implementation of the BEINGs
23100	ideas, isolating those due to poor programming from those due to
23200	poor ideas, enough may be learned to build the next system one
23300	qualitative step closer to this ideal.
23400		It is in this spirit that BEINGs
23500	are now contrasted against  the  concepts  of  ACTORs, CLASSes,
23600	FRAMES, HACKER, formal AP systems, and macro expansion schemes.
23700		ACTORS [Hewitt]  provided  the  key  concept  of  integrating
23800	uniformity  of  construction  with  sophistocation of behavior. There
23900	is a continuum, among modular knowledge schemes, of standardization of
24000	"message" types between modules. ACTORs have no restriction whatsoever
24100	on this format. Each module has its own, unique parts (types of
24200	answers). So each ACTOR must be aware of all the parts (message formats)
24300	of all the  ACTORs it ever is going to communicate with. 
24400	Adding a new module is thus conceptually intricate as
24500	well as practically difficult. CLASSes [..........] have a few standard
24600	parts, and the modules are arranged in groups, each of which has its
24700	own additional types of parts. Thus a module can ask ⊗4any⊗* other module
24800	one of a few universal questions, and it can ask any module in its group
24900	an additional set of questions. If it is permitted to know about other
25000	groups' special parts, then the same adding problem recurs. If it is
25100	denied such knowledge, it cannot access much of the knowledge in the
25200	pool.  If one requires a completely universal set of message types, then
25300	most of them will be irrelevant to most modules. This is the price which
25400	BEINGs pay. Later, it will be shown that this superfluity is real and is
25500	marginally tolerable. The most devastating criticism of striving for a
25600	universal set of module questions is that all this does is push all the
25700	non-uniformity down into the values of these parts. The only retort is
25800	empirical: if a good partitioning of the questions can be found, then
25900	the internal structure of each part with the same name will be comparable,
26000	and the only communication necessary will be simple questioning of
26100	modules's parts.
26200	
26300		FRAMES [Minsky] seems superficially similar  to  BEINGs,  and
26400	are so amorphous that they actually could subsume BEINGs. There is a
26500	deep difference of philosophy and of intended usage, however.
26600	FRAMES intentionally have default values already (with no processing)
26700	filled in  for each frame, and replaced only when  necessary.
26800	This  is  akin  to  automatic  programming by blind debugging, but is
26900	antithetical to the fastidious bookkeeping BEINGs philosophy.  As  an
27000	example,   consider   the   writing   of  a  short,  recursive,  list
27100	manipulation LISP program (reverse, flatten, assoc, alternate,  etc.)
27200	A human, consulting the proper frame in his head, knows to ignore the
27300	base step for a while, then fill it in, usually  as  ⊗4if  NIL,  then
27400	NIL⊗*.  The
27500	human makes this default synthesis, tries out the program, and  looks
27600	closer  (to fill in this "slot" properly) only if something calls his
27700	attention to it (such as a LISP error message:
27800	NON-NUMERIC ARG  ⊗4NIL⊗*, e.g., if what was really needed was the base
27900	step ⊗4if NIL, then 0⊗*).
28000	A BEINGs system would
28100	also  defer working on the base step, but could -- and would -- place
28200	a note about that deferral into the assertional warning base.  Before
28300	thinking  it  was  finished,  the  system  would  attend to that note
28400	carefully. This is not a criticism of FRAMES:   
28500	they  are  meant  to  be  a
28600	construct  to  model  perception,  and  therefore the default concept
28700	makes sense for them. BEINGs are clearly non-anthropomorphic in their
28800	internal  workings,  and  would  be very unlikely to occur as a human
28900	perceptual mechanism.
29000		HACKER [Sussman] differs from BEINGs in the same  qualitative
29100	way.  The orientation of HACKER is to put together pieces of programs
29200	into something close to the final desired target, then  try  and  run
29300	it.  When  errors result, they are analyzed and then patched.  BEINGs
29400	is oriented toward writing bug-free code; what it writes must  always
29500	coincide  with its internal specifications of that code. The user may
29600	later change his mind, and a BEINGs system must be able to modify its
29700	own  programs,  but  this  process  is much better defined than blind
29800	debugging. On the other  hand,  if  a  BEINGs  system  does  have  an
29900	unexpected bug in it, it may not be able to recover from it. One
30000	way to overcome this would be to include special recover-from-bugs
30100	BEINGs.
30200		The  formal  manipulation  systems which also synthesize code
30300	are so different from BEINGs, that it is difficult to  compare  them.
30400	These  logical systems (e.g., [Luckham]) attack an entirely different
30500	problem.  Their task is specified rigorously  in  advance,  and  they
30600	proceed  formally  to  search  for  a  solution  program.  BEINGs are
30700	designed to work on a much higher level, heuristically.  Each  action
30800	is  implicitly justified by the fact that the user can later describe
30900	to the system
31000	what is wrong with the program it's generated. BEINGs  should
31100	thus  be  tolerant of user ambiguity and error.  Also, BEINGs are not
31200	limited to automatic programming.
31300		Like  ⊗4any⊗* AP system which writes structured programs, the
31400	external behavior  of  a  BEINGs  system  applied  to  this  task  is
31500	reminiscent  of  macro  expansion regardless of ⊗4what⊗* the internal
31600	BEING  interactions  are.  One  major  distinction  between  the  two
31700	concepts is when and how the macros are expanded. Traditional answers
31800	are:  at  compile  time,  by  rigid   substitutions   (although   not
31900	necessarily  context-free.)  BEINGs  systems expand their "macros" at
32000	times they choose, using knowledge gleaned from each other  and  from
32100	the  user. For example, consider a series of macro calls occurring in
32200	the code: (m1)(m2)(m3). A macro expander could expand these in any order,
32300	and the three activities could go on simulatneously, with no interference
32400	or change in the final code. BEINGs would try to find some task common
32500	to all three calls, and work on that first. The order of which to
32600	first expand fully would be carefully weighed, 
32700	and during that expansion new
32800	information would be learned which could affect the expansions of the
32900	other two function calls. The final code would not simply be the APPEND
33000	of the expansions of m1, m2, m3.  As macro expansion schemes increase
33100	in sophistocation, it may someday be appropriate to refer to BEINGs as
33200	such a system.
     

00100	.NEXT PAGE
00200	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},REALITY:  EXAMPLES)
00300	⊗24. REALITY:  EXAMPLES⊗*
00400		This  section  presents  examples  of  the following:       a
00500	programming knowledge BEING, an explanation of what  happens  when  a
00600	BEING  is called, a concept formation knowledge BEING, a descriptions
00700	of a piece of the user-PUP6  dialogue,  and  some  justification  for
00800	using functions, call-by-name, demons, and assertions. Although these
00900	examples are meant to clarify  the  preceding  section's  theoretical
01000	ideas, they are all drawn from the actual PUP6 system.
01100		4.1.   OBTAIN_USABLE_INFORMATION  is  a  typical  high-level,
01200	domain-independent  BEING.    The  WHEN  part  consists  of predicate
01300	"feelers"  which  sample  the  world  and  report   their   qualities
01400	numerically.   A reason is supplied with each feeler:
01500	an English sentence stored for the benefit of inquisitive users.
01600	The numbers are
01700	then simply added to decide how a propos the  BEING  is  at  present.
01800	This  scheme  is  adequate  but  undesirable;  one would like them to
01900	discuss descriptions of what they encounter; but  the  WHEN  part  is
02000	used  only  to  break  ties  between BEINGs vying for control, and it
02100	usually doesn't matter what order they go in.  Thus  a  simple,  fast
02200	method  of  selection suffices.  This particular BEING (whose parts
02300	are exhibited on pages 10 and
02400	11) has feelers which respond that it is ⊗4always⊗* an  undesirable
02500	(-10)  thing  to  do, but ⊗4may⊗* be indicated (+111) if there exists
02600	new but not yet usable information. The possible final WHEN
02700	values are thus 111, 101, and -10. These numbers, like all the parts
02800	of all the BEINGs initally in PUP6, were decided upon and inserted by
02900	hand.
03000		The   IDEN   parts   are  collected  together  into  a  large
03100	translation table.  When  a  form  ⊗4LI⊗*  must  be  translated,  the
03200	TRANSLATE  BEING goes through this table, asking each IDEN part if it
03300	claims to recognize ⊗4LI⊗*. Each IDEN runs its  own  little  program,
03400	typically  some  type of pattern match involving ⊗4LI⊗* and the state
03500	of the world, to answer this question.  Some measure of  goodness  of
03600	match  is  also  reported.   If  there  is  more  than one responder,
03700	CHOOSE-FROM picks the one with the highest priority of  match.    The
03800	winner runs a little program which ultimately returns a BEING-call or
03900	a constant as the translated value of ⊗4LI⊗*. This program might call
04000	other  BEINGs,  often  calls  TRANSLATE  several times recursively on
04100	parts   of   ⊗4LI⊗*.     Now   examine   the   IDEN   part   of   the
04200	OBTAIN_USABLE_INFORMATION  BEING  (next page).
04300	There are just two classes of phrases that this BEING can recognize.
04400	If two conditions are met,
04500	it says to ⊗4call⊗* OBTAIN-USABLE-INFORMATION with, as argument,  the
04600	result of calling TRANSLATE on the second element of ⊗4LI⊗*.
04700	If some BEING or user wants to find out more about anything, then 
04800	this BEING can be called with that thing as argument.
04900		The EFFECTS parts of each BEING are similarly collected  into
05000	one  table  to  facilitate  asking all BEINGs simultaneously "Can you
05100	cause X to occur?" Each EFFECTS part examines X and  the  world,  and
05200	either  replies No, or else returns a little program (involving calls
05300	and constants) which  should  produce  the  effect,  with  a  certain
05400	probability.   This program will probably involve a call to the BEING
05500	itself. The BEING below shows that it should be called to acheive the
05600	existence of new, usable information (see the MAIN:EFFECTS part, page
05700	11).
05800		The WHAT, HOW, and  WHY  parts  are  mainly  for  the  user's
05900	benefit.   When  a  choice  between  BEINGs  must  be made, the WHEN,
06000	AFFECTS,  and  COMPLEXITY-VECTOR  parts  are  queried.    If  a  new,
06100	manipulated   version   of   the   BEING   must   be   created,   the
06200	SPECIALIZATIONS,   ENCODABLE,    DATA-STRUCTURE,    PREDICATE,    and
06300	FORM-CHANGING  parts  might  be  relevant.   If the BEING fails, some
06400	BEING speicified in the ALTERNATIVES or GENERALIZATIONS parts might
06500	be tried.
06600		In the current case, the COMPLEXITY-VECTOR says that it is of
06700	average difficulty to call, its descendants may (.5 chance)  call  it
06800	back,  it has an average chance of success and cost of attempting it,
06900	and there is no (.1) good reason to defer it any longer.
07000		The  AFFECTS  part  of the OBTAIN_USABLE_INFORMATION BEING is
07100	clear. One BEING is definitely called, and four others might be. 
07200		The  absence  of  some parts, like DATA_STRUCTURE, PREDICATE,
07300	and NLAMBDA, indicate that these qualities don't apply.  The  absence
07400	of  other  parts,  like  SPECIALIZATIONS and ALTERNATIVES, indicate a
07500	lack of thoroughness in filling out unneeded BEING parts.
07600		The   META-CODE   has  us  choose  from  the  following  four
07700	alternatives,    each    of    which    is    itself     a     BEING:
07800	Get_Brand_New_Information  (in  English,  from  the  user), Translate
07900	something    (transform     from     English     to     BEING-calls),
08000	Analyze_The_Implications  (of some existing, translated information),
08100	Extract_a_Relevant_Subset   (of   the   existing   information)    to
08200	concentrate upon.
08300	Calls are nondeterministic only when the BEING doesn't know exactly
08400	which BEING to call. If the ⊗4set⊗* of possible choices is known, as
08500	in this case, then CHOOSE-FROM is called with the choice set explicit.
08600	If even this isn't known, then CHOOSE-FROM must query the EFFECTS
08700	parts of all the BEINGs in the system.
08800		Below are exhibited the actual representation of  this  BEING
08900	in  PUP6,  and  the  function  which  would  be  executed  if it were
09000	⊗4called⊗*.
09100	
09200	.SELECT 5
09300	.BEGIN NOFILL
09400	
09500	
09600	⊗4↓_PART_↓    ↓_actual value of the part for OBTAIN:USABLE:INFORMATION_↓ ⊗*
09700	
09800	IDEN ((if you see: (AND (EQUAL (CAR LI)
09900		  		    	OBTAIN:USABLE:INFORMATION)
10000		 	        (EQUAL (LENGTH LI)
10100					 2))
10200	       then return: (OBTAIN:USABLE:INFORMATION (TRANSLATE (CADR LI))))
10300	      (if you see: (MATCH ( FIND OUT MORE ABOUT ANY1)   LI)
10400	       then return: (OBTAIN:USABLE:INFORMATION ANY1)))
10500	BEING T 
10600	EXPLICIT:ARGS (U) 
10700	WHAT ( OBTAIN SOME INFORMATION WHICH CAN BE USED) 
10800	HOW ( OBTAIN NEW FACTS ABOUT OLD INFORMATION, OR OBTAIN TOTALLY
10900	     NEW INFORMATION) 
11000	WHY ( PUP HAS NO MORE INFORMATION THAT IT CAN USE TO PROGRESS) 
11100	WHEN ((if T then add in -10 (SINCE THIS IS AN EXPONENTIALLY-GROWING,
11200		      			BAD THING TO DO IN GENERAL))
11300	      (if NEW:INFO:LIST then add in 111
11400	             	(BECAUSE WE SHOULD WORK ON UNASSIMILATED NEW 
11500		                      INFORMATION IF THERE IS ANY)))
11600	META:CODE (DO
11700			 (CHOOSE:FROM ((TRANSLATE U)
11800	   			       (GET:NEW:INFORMATION U)
11900				       (ANALYZE:IMPLICATIONS U)
12000				       (EXTRACT:RELEVANT:SUBSET U)))
12100		   BECAUSE
12200			 (WE CAN ONLY TRY TO OBTAIN USABLE 
12300				    INFORMATION IN ONE WAY AT A TIME))
12400	EXPLICIT:ARGS:CHECK T 
12500	MAIN:EFFECTS ((to get (NEW INFO ANY1)
12600	               do (OBTAIN:USABLE:INFORMATION ( ANY1)))
12700	              (to get (USABLE INFO ANY1)
12800		       do (OBTAIN:USABLE:INFORMATION ( ANY1)))) 
12900	AFFECTS       ( (CHOOSE:FROM CALLED)
13000		        (TRANSLATE POSSIBLE:CALLED)
13100	 	        (GET:NEW:INFORMATION POSSIBLE:CALLED)
13200		        (ANALYZE:IMPLICATIONS POSSIBLE:CALLED)
13300		        (EXTRACT:RELEVANT:SUBSET POSSIBLE:CALLED) )
13400	COMPLEXITY:VECTOR (.5 .5 .5 .5 .1) 
13500	
13600	.SELECT 1
13700		4.2. When a BEING is ⊗4called⊗*, its parts are assembled into a
13800	function which is then executed. Here is the ⊗4FUNCTIONAL⊗* form of the
13900	OBTAIN:USABLE:INFORMATION   BEING:
14000	.SELECT 5
14100	
14200	(OBTAIN:USABLE:INFORMATION
14300	  (LAMBDA (U FN:VALUE FINAL:CO:REQ)
14400	      (PROG1 
14500	          (AND 
14600	              (SETQ BEING:STACK (CONS OBTAIN:USABLE:INFORMATION BEING:STACK))
14700	              (PUT OBTAIN:USABLE:INFORMATION SPEC:WHY BECAUSE)
14800	              (EVERY (APPEND CURRENT:DEMONS USER:INTERRUPT:DEMONS)
14900	                     (QUOTE APPLY*))
15000	              (SETQ BECAUSE
15100	             	   (QUOTE (WE CAN ONLY TRY TO OBTAIN USABLE 
15200	                              INFORMATION IN ONE WAY AT A TIME)))
15300	              (CHOOSE:FROM (QUOTE ((TRANSLATE U)
15400	           		           (GET:NEW:INFORMATION U)
15500				           (ANALYZE:IMPLICATIONS U)
15600				           (EXTRACT:RELEVANT:SUBSET U)))))
15700	          (SETQ BEING:STACK (CDR BEING:STACK)))))
15800	.END
15900	.SELECT 1
16000	
16100		The  process of assembling the BEING parts into a function is
16200	straight-forward.  First, the explicit arguments (those global to the
16300	BEING)  are  bound. The implicit arguments (those local to the BEING,
16400	like PROG variables) are initialized. The name of the BEING is pushed
16500	onto  the  BEING  control  stack  (pointing  to  its caller), and any
16600	newly-activated  demons  are  pushed  onto  the  demon  stack.   The
16700	ARGS-CHECK  predicates  are  evaluated.  Then PUP6 works to make each
16800	PRE-REQUISITE true in the world.  Each COMMENT is evaluated, then the
16900	CO-REQUISITES,  META-CODE,  and  current  demons  all are executed in
17000	pseudo-parallel.  Each POST-REQUISITE is then satisfied.  Since these
17100	activities are all embedded in an AND, any of them may cause the
17200	entire BEING to halt and fail, simply by returning NIL.
17300	In both cases, just  before  exiting,  the  demon
17400	stack is popped and the BEING stack is updated (usually just popped),
17500	and control passes to the delegated BEING (usually the one who called
17600	this  BEING,  at  the  state  when  he  called  it.)  A fancy context
17700	mechanism was available but not actually needed.
17800		The function which assembled all the BEINGs exploited the
17900	fact that it operated only at  system load time. Thus if the BEING 
18000	had no new DEMONs to activate, all the corresponding demon-stack
18100	manipulations could be omitted. Optimizations like these are clear
18200	from comparing the functional form and the description of how it
18300	should be created (see above).
18400	Another example in this BEING is that no CO-REQUISITES 
18500	occur, so no parallel processing need be simulated. 
18600		4.2 PARTITION_A_DOMAIN is a high-level, domain-specific BEING
18700	whose basic idea is to divide up a space into  categories.  Only  two
18800	BEING   parts   are   filled   in   here   which   were  absent  from
18900	OBTAIN_USABLE_INFORMATION; namely, SPECIALIZATIONS  and  DEMONS.  The
19000	SPECIALIZATIONS part says that to write a specific version of itself,
19100	a few decisions must be made. The results  will  then  indicate  what
19200	pieces  of  code  get  assembled together to form the new BEING.  The
19300	partition may be only partial (an element of the domain belongs to no
19400	class  of  the partition), only weak (an element belongs to more than
19500	one class), and, most importantly, the specialized BEING should  work
19600	by  repeatedly doing some of the following three activities: accept a
19700	class-name from the user and guess some of its elements, accept an 
19800	element from the user and try to guess which class it belongs to,
19900	or accept an <element, class-name> pair. Other BEINGs know
20000	about these accepting, guessing, checking activities.
20100		The  DEMONS  part says that during the partitioning, the only
20200	new demon to keep active is the one  called  Fringe_of_Consciousness.
20300	This   last  concept,  named  in parody of an "impossibility"
20400	mentioned in [Dreyfus], is worth  exemplifying.   In  the  course  of
20500	writing  GI,  the  system  learns  that  the  main  task  is  one  of
20600	grammatical inference.  The Grammatical_Inference BEING then  asserts
20700	that  if  the  user ever mentions the word TEST, he may actually mean
20800	PARSE.   This is placed in the IDEN part of the TEST  BEING,  and  is
20900	therefore   only  demonized,  waiting  on  the  periphery  of  PUP6's
21000	concentration.   It is in fact triggered later in the dialogue, as an
21100	inference surprising to the user.
21200		4.4.  The dialogue to synthesize CF begins by PUP6 asking the
21300	user  for  any  task.   The user replies, ⊗4Write a program which does
21400	concept formation⊗*. There are many decisions that PUP6 knows about in
21500	writing  a  specialized  concept formation program [Hempel], 
21600	and it manages to
21700	defer them all.   For example, it must choose between classificatory,
21800	comparative,  and metrical concept formation. Since all three involve
21900	partitioning a domain of examples, PUP6 decides  it  can  defer  this
22000	choice  until  after code for the partitioning is synthesized.    The
22100	effort of the system is now  directed  toward  this  "piece"  of  the
22200	program.  When it is completed, an hour or two later, the system asks
22300	the user to make this decision. When he picks the first  alternative,
22400	which  involves ⊗4only⊗* partitioning,  the  system  prints that it has
22500	finished the entire CF task, and dumps the newly created BEINGs  onto
22600	a file.
22700		4.5. Earlier, the claim was made that the presence of popular
22800	AI language  features did not detract from the combinatorial behavior
22900	of the system, since BEINGs subsume each mechanaism used. This will
23000	now be sketched. Direct call by name may be viewed as a trivial type
23100	of pattern-directed call, 
23200	where each BEING can recognize its own name. See the IDEN part of the
23300	OBTAIN:USABLE:INFORMATION  BEING, for example.
23400		A demon
23500	in PUP6 is merely a function which gets executed periodically,
23600	and may occasionally trigger a BEING. This could  be  replaced  by  a
23700	BEING   whose   EXPLICIT:ARGS:CHECK   part  contains  the  triggering
23800	predicate, and whose META:CODE is simply a call by name  directly  to
23900	the  BEING  which  is  supposed to be activated.  
24000		An assertion can be
24100	viewed as a BEING containing  only  an  IDEN  part;  when  the  BEING
24200	recognizes a form which matches it, it returns the fully instantiated
24300	assertion. 
24400		A function is equivalent to a BEING with only a  META:CODE
24500	part;  one  knows  nothing about it before executing it.  
24600		Notice that
24700	the overheads saved by these mechanisms are substantial. For example,
24800	assertions replace an entire BEING call by a single CDR evaluation.
24900		The reader may have observed  the  static  quality  of  these
25000	examples,  and  wished  for  one of BEINGs in action, passing control
25100	back and forth in order to do something. But to present a  reasonable
25200	example   of  BEINGs  interacting,  it  is  necessary  to  understand
25300	something about the target  task.   Thus  we  describe  PUP6  in  the
25400	following  section,  including  how  the target task CF evolved. Then
25500	comes the dynamic example, in section 6.
     

00100	.NEXT PAGE
00200	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},THEORY:  DESIGN)
00300	⊗25. THEORY:  DESIGN⊗*
00400		A  highly  polished  presentation  of  a  large  system omits
00500	mention  of  the  design  and  implementation  mistakes.    This   is
00600	unfortunate;  many  decisions  which seem arbitrary are the result of
00700	painful re-working, and conversely.  The reader may  relax;  he  will
00800	find nothing polished about this treatment.
00900	
01000		Once  the  task  (automatic  program  synthesis from specific
01100	dialogue) was decided  upon,  considerable  attention  was  spent  on
01200	choosing  an  appropriate  domain  of  target  programs.  The choice,
01300	inductive inference  (II), merits  discussion.  The  obvious
01400	difficulty  appears  to  be  the complexity of the programs involved:
01500	they  are  two  orders  of  magnitude  larger  than  any   previously
01600	synthesized  programs. But there are four big attractions:
01700		(i)
01800	A  wide  range  of  complexity  exists,  from  a  one-page   sequence
01900	extrapolator   to   Meta-Dendral.
02000		(ii)   Each   increasingly
02100	sophisticated II program  uses  many  of  the  concepts  embodied  in
02200	simpler  II programs.
02300		(iii) If a super-human target program is
02400	ever written, it could itself contribute to the  field  of  Automatic
02500	Programming! (For those reading this in the 1970's, this is humorous.
02600	For those later readers, it may be commonplace.)
02700		(iv)  Since people (especially those who write
02800	AI  programs) are the inductive
02900	inference experts, our reliance on  introspection  is  as
03000	valid  --  and potentially as valuable -- as chemists' protocols were
03100	to Dendral.
03200		After  studying  many  sample  programs  from  the II domain,
03300	sequence extrapolation [Pilvar] seemed the most reasonable  beginning
03400	task. It was quickly learned that this was too easy: humans have only
03500	a few techniques for extrapolating  sequences,  and  a  very  limited
03600	capacity   for   composing   them.   Thus  a  rather  rigid  sequence
03700	extrapolator writer may be capable of generating  a  large  class  of
03800	super-human programs (see section 4.2 on
03900	Sequence-Extrapolator-Writer, in [Green]).
04000		The  next  candidates  were grammatical inference and concept
04100	formation [Hempel].
04200	Determined not to choose too simple  a  task  again,  the
04300	latter program was finally decided upon.  The particular target was a
04400	variant of [Winston]. To make the goal more tractable, certain  parts
04500	of   Winston's   description   were  ignored,  namely  the  heuristic
04600	graph-matching section, and the uniformity requirement that relations
04700	on features be functionally indistinguishable from features.
04800	This last phrase means that CF can store (MUSTNOT (SUPPORTS a b))
04900	differently from the representation of simple 
05000	features like (TOUCHES a c).
05100		It seems instructive now to describe how the  target  program
05200	should operate. It repeatedly scans a scene and tries to name it. The
05300	scene is broken into a set of features and a set of objects. Each 
05400	feature is  a  relation
05500	on  one  or  more  objects  in  the  scene.  Internally,  the program
05600	maintains a model for each differently-named 
05700	concept it has ever encountered. "Concept" here is used technically, to
05800	indicate a particular data structure maintained by the target program.
05900	The  model  contains  a  description  of  the objects expected in the
06000	scene, a set of features which must be present in the scene (else  it
06100	can't  be the same as this concept), a set of features which must not
06200	be present in the scene, and a set of features which may or  may  not
06300	be  present.  Thus  a model is like an archtypical scene plus a name.
06400	Each time the program is confronted by a new scene, the program  must
06500	scan its models until it finds one which matches it. That is, all the
06600	model's MUST features are present, and all the MUSTNOT  features  are
06700	absent  from  the  observed scene. It informs the user of this guess,
06800	and accepts the proper concept name. If it  guessed  incorrectly,  it
06900	modifies its models. The wrong guess model may have features added to
07000	its MUST or MUSTNOT sets; the correct concept name model may have  to
07100	be  modified or (if it's a new concept) created and inserted into the
07200	list of models.  See the flowchart on page A4.7.
07300	.B
07400	
07500	For example, part of a scene might be:     OBJECTS a,b,c,d
07600		(GREEN a)(BLUE c)(TOUCHING c d)(SUPPORTS a c)(SUPPORTS b c).
07700	
07800	A model for an arch might be:      OBJECTS a,b,c
07900		MUST 	(SUPPORTS a c)(SUPPORTS b c)
08000		MUSTNOT (TOUCHES a b)
08100		MAY	(GREEN a)(WEDGE c)(PRISM a)(BLOCK b)(PARALLEL a b)
08200	.E
08300		Suppose  that the target program reads in the above scene and
08400	tries to match it to  the  above  model  for  consistency.  The  MUST
08500	relations  should  all  be  present.   Yes,  the  scene  does contain
08600	(SUPPORTS a c) and (SUPPORTS b c). Next, the MUSTNOT  relations  must
08700	be absent from the scene. Sure enough, (TOUCHES a b) isn't there.  So
08800	the model and scene are consistent.  If the user verifies this guess,
08900	then  the MAY set is augmented with (BLUE c) and (TOUCHING c d), and
09000	the OBJECTS set is augmented with "d."
09100	If the user denies that the scene is an arch, the target program
09200	sees if there are any relations in the model's MAY set which do not
09300	occur in the scene. If so, one of them (e.g., (PARALLEL a b)) will
09400	be transferred from the MAY to the MUST set.  If no such feature 
09500	existed, the program would look for a feature present in the scene
09600	but absent from all sets of the model (e.g., (BLUE c)), and insert
09700	it into the MUSTNOT set.  Also, if the user disagreed with the guess,
09800	he would be asked what the true name of the concept was, and that
09900	concept's model would have its MAY set augmented by any new 
10000	features in the scene. Any features on its MUST or MUSTNOT sets
10100	which contradicted the scene would be transferred to the MAY set.
10200		After the target concept formation program was specified,  it
10300	was trimmed and then rewritten as a structured program [Gadwa]. Next,
10400	a complete dialogue was  simulated  between  the  user  and  a  human
10500	programmer  (referred to as the system-player) playing the role of an
10600	"intelligent"  automatic  programming  system  (similar   to,   e.g.,
10700	[Balzer]).      The   system-player   kept   careful  records  as  he
10800	programmed, and tried to create a bug-free  structured  program.  The
10900	dialogue  was  then annotated:     after each user response, comments
11000	were inserted which described the "states" the system-player had gone
11100	through before printing his next response.  This included blind paths
11200	which were tried, use of outside world knowledge,  and,  in  general,
11300	was  meant  to  be  the "intelligence" necessary to do the task.  The
11400	fear was that a system could be built which synthesized  the  concept
11500	formation  program,  and  yet  was  so unintelligent that nothing was
11600	learned from it. (see section 4.1 on PW1, for example,  in  [Green]).
11700	Hopefully,  any  system  which  (i) got the target program correctly,
11800	(ii) followed our initial dialogue, and, most importantly, (iii) went
11900	through  the  same  line of reasoning that our comments indicated the
12000	system-player 
12100	followed, would be far along the road  toward  intelligence.  A
12200	corollary of this incremental annotated protocol approach is that the
12300	abilities of the user must coincide with those  of  the  subject  who
12400	participated  in the protocol (see also [Woods]). The system would be
12500	far along the road toward automatic programming if it also  (iv)  was
12600	able  to  write  CF  from several dialogues, from several users, with
12700	little preparation. PUP6 was not designed to do this, and in the  end
12800	it  proved to be a serious deficit.  Henceforth, ⊗4protocol⊗* will
12900	refer to this user-player / system-player simulated dialogue.
13000		The target user must be familiar
13100	with  LISP,  well-grounded  in  computer  science,   and   have   the
13200	input/output  behavior  of  the  concept  formation (CF) program very
13300	clearly in his mind. The natural language front  end  is  so  brittle
13400	that  the user must also phrase his responses very similarly to those
13500	of the original protocol subject.  This  factor  prevented  dialogues
13600	from multiple users from being successful.
13700	
13800		At  this  point,  most  of  the  ideas described in section 3
13900	surfaced, including a rough initial set of BEINGs.  Each one had  not
14000	much  more  than  a  name and a vague description of what it must do.
14100	The  dialogue  was  cycled  through  again,  painstakingly,  and  the
14200	comments  were  replaced  by a description of which BEINGs would call
14300	which other BEINGs, why, and the results  of  each  such  call.   The
14400	constraints   on   each  BEING  thus  grew,  sometimes  changed,  and
14500	occasionally a new BEING or  BEING  part  had  to  be  added  to  the
14600	community.  This  process  was  long  (200 hours) and produced a long
14700	(200-page) protocol, actually a hand trace of the  system  execution.
14800	About  eighty  BEINGs  were needed:  a dozen domain-specific ones and
14900	the rest  domain-independent  programming  knowledge.   About  thirty
15000	different  BEING  parts  were  called  for,  and  they  are listed in
15100	Appendix 1.  The next appendix describes each BEING briefly; only the
15200	most important knowledge is mentioned.
15300		A result of  this  method  of  incremental  specification  of
15400	BEINGs  is that each BEING has only those parts which are going to be
15500	used sometime during the ensuing dialogue. This seemed too  specific,
15600	so  some  effort  was  spent  filling out parts that weren't strictly
15700	necessary to write the  concept  formation  program.    Perhaps  more
15800	careful  attention  to  this activity would have made the system more
15900	tolerant of changes in the dialogue. During the course  of  massaging
16000	PUP6  into  writing  the  other  target programs, very few additional
16100	parts had to be added to existing BEINGs. Typically,  either  an  old
16200	part had to be generalized or else a new BEING created. After writing
16300	CF, GI, and INF, there are now an even hundred BEINGs in PUP6.
16400		The data on how filled out each BEING was -- and had to be --
16500	is presented in several  forms,  here  and  in  the  appendices.   In
16600	Appendix 1, next to each BEING part is the percentage of BEINGs which
16700	had to have this part specified for them. Appendix 3 reveals how each
16800	BEING  was  actually  used,  including  the number of its BEING parts
16900	which exist and were called upon during a dialogue. On  the  average,
17000	each  BEING  part  was present in 36% of all BEINGs, and, also on the
17100	average, each BEING had 10.5 of its 29 parts specified. This says 
17200	that each BEING was actually asked a third of all possible questions
17300	and that each question was needed in about a third of all the BEINGs.
17400	This is just marginally tolerable; if the percentages were much
17500	lower, then the idea of grouping the BEINGs and assigning each group
17600	its own distinct set of questions would be clearly called for.
17700		The  principle that "everything is BEINGs" was relaxed in the
17800	interests of absolute CPU time and feasibility  of  coding.   Besides
17900	BEINGs,  PUP6 employs functions, demons and an assertional data base.
18000	During  the  programming,  100  small  functions  were   written   to
18100	supplement  the  language.   Most  were  typical  current AI language
18200	features [Bobrow] (pattern-matching, demons, special data types),  or
18300	tiny additions to INTERLISP [Teitelman] (flatten, set-difference), or
18400	functions      which      manage       BEINGs       (add-a-new-being,
18500	print-a-being's-parts).   Many of these features were simplified (and
18600	speeded up) by using the knowledge that PUP6 was to be an AP  system.
18700	For  example, all the different types of assertions that an AP system
18800	might want to make deal with different concerns of programming.  Thus
18900	a  group  of about forty different assertion patterns could be fixed,
19000	each one becoming a named  list;  this  almost  eliminated  searching
19100	during retrieval from the assertional base.
19200		The initial  programming  took  only  a  hundred  hours,  but
19300	several  times that amount of work was required before the system was
19400	debugged  to  the  point  of  successfully  following  the  annotated
19500	dialogue.
     

00100	.NEXT PAGE
00200	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},REALITY:  EXAMPLES)
00300	⊗26.  REALITY:  EXAMPLES⊗*
00400	
00500		An example of the PUP6 community of BEINGs interacting will now
00600	be presented. Let's jump one third of the way into the dialogue which
00700	writes  CF. The system learns it must compare the input scene against
00800	its internally stored models of concepts, until it  finds  one  which
00900	doesn't  fail  the  comparison.   It  asks the user what it means for
01000	scene S to fail the comparison to model M. The user  replies,
01100	whenever M  is  incompatible  with  the  observed  features  of  S.
01200	The IDEN part of the
01300	CONTRADICTS BEING recognizes this sentence pattern, and transforms it
01400	to 
01500	.NOFILL
01600	(FORSOME  F  IN M_FEATURES (specialized:contradicts F S_FEATURES)).
01700	.FILL
01800	The BEING
01900	which inserts this into the synthesized code requires that  the  user
02000	pick  some  proper  name  for  the function specialized:contradicts;
02100	this will be a streamlined contradiction test written by the
02200	CONTRADICTS BEING.  Say the user reponds by calling it IMPOSS. This naming
02300	and specializing is central to BEING creation: a BEING recognizes an
02400	instance of itself, and decides either to insert a call to itself or
02500	else to insert a call to a specialized version of itself.  If any
02600	nontrivial decisions must be made, and can be settled at synthesis
02700	time, then the latter alternative is chosen.  CONTRADICTS is too 
02800	general a BEING to be called in an inner loop, so its content will
02900	be hammered out at synthesis time. On the other hand,
03000	FORSOME is so primitive that no  specialized
03100	version  of  it  is  written normally. 
03200		Here is the way this piece of the dialogue actually appears.
03300	The user's reponses are italicised.
03400	The system informs the user of
03500	where it is by simulating a cursor pointing into a graph  of  program
03600	code.  This  is  analogous  to  the textual and dynamic indices which
03700	[Dijkstra] suggests. 
03800	.NOFILL
03900	
04000	PLEASE TYPE IN A LOGICAL EXPRESSION WHICH IS TRUE WHEN WE TERMINATE
04100	       THE LOOP, AND IS FALSE OTHERWISE.
04200	
04300	SHOULD I DISCUSS RAMIFICATIONS?⊗4NO⊗*
04400	
04500	USER: ⊗4(ANY RELATION IN POSSIBLE:NAME:OF:CLASS:RELNS IS INCOMPATIBLE
04600	    WITH ELEMENT:RELNS)⊗*
04700	
04800	PUP WANTS USER TO TYPE IN NAME FOR  SPECIALIZED VERSION OF CONTRADICTS.
04900	
05000	USER: ⊗4IMPOSS⊗*
05100	.FILL
05200		Later in the  dialogue,  PUP6  decides  it  must
05300	expand the function IMPOSS. The CONTRADICTS BEING is again called on; this
05400	time  it  is  asked  how  to  write  a  specialized  version   of   a
05500	contradiction  test.  It  replies that SOME_OF the following types of
05600	contradiction  may  occur:        PROBABILITY:0,  PROBABILITY:1,  and
05700	PROBABILITY:ε(0,1).    This   is   the  germ  of  the  idea  for  the
05800	MUSTNOT/MUST/MAY categorization of features. The SOME_OF BEING  takes
05900	control,  and  asks  if  the  decision can be deferred.  The DEFERRAL
06000	BEING looks about, first asking if there is  any  non-null  piece  of
06100	code  that  all three have in common.  This fails, and eventually the
06200	DEFERRAL BEING reports failure.  SOME_OF sees it has  no  basis  upon
06300	which  to  form  a  guess,  and  wants somebody to ask the user.  The
06400	ASK_USER BEING takes over, and trivially finds out what it is that PUP6
06500	wants  to  learn.  The names of the three choices are so cryptic that
06600	their WHAT and HOW parts are printed out to  the  user,  as  well  as
06700	their names.  The user types back his choices, in our case all three.
06800	SOME_OF  composes  three  new  function   calls,   separated   by   a
06900	conditional:
07000	.B
07100	
07200	(COND ( (IS_OF_TYPE         F   PROBABILITY:0_PART_OF_M_FEATURES)
07300		(PROBABILITY:0_CONTRADICTION    F    S_FEATURES))
07400	      ( (IS_OF_TYPE         F   PROBABILITY:1_PART_OF_M_FEATURES)
07500		(PROBABILITY:1_CONTRADICTION    F    S_FEATURES))
07600	      ( (IS_OF_TYPE         F   PROBABILITYε(0,1)_PART_OF_M_FEATURES)
07700		(PROBABILITYε(0,1)_CONTRADICTION  F  S_FEATURES)))
07800	.E
07900	TRICHOTOMY recognizes this as a split on a function's  values
08000	being  =0,  =1,  or  between  zero  and  one.   It  asks whether this
08100	particular  function  can  only  range  over  the   interval   [0,1].
08200	PROBABILITY  answers  affirmatively,  so  SOME_OF  replaces the final
08300	IS_OF_TYPE test by the constant T.  Later on, PUP6 must  worry  about
08400	the  other  two  tests, and about the three contradiction predicates.
08500	These latter entities know (their ENCODABLE  parts  tell  them)  that
08600	they  are  immediately encodable. A probability=0 contradiction means
08700	that arg1 must not occur in the  world  arg2  yet  it  does.  So  the
08800	META-CODE  of  the  PROBABILITY:0_CONTRADICTION  BEING  is defined as
08900	(MEMBER arg1 arg2).  This corresponds to a MUSTNOT feature F which is
09000	present  in  the  world  (in  the  set of S_FEATURES of the scene.) A
09100	probability=1 contradiction occurs when a feature arg1 must occur  in
09200	the  world  arg2,  yet  it  doesn't. So its definition is simply (NOT
09300	(MEMBER arg1 arg2)).  It is impossible for a feature with probability
09400	in  (0,1)  to  be  in  contradiction  with any world (lacking negated
09500	features), so this third predicate is defined as  the  constant  NIL.
09600	That  is,  if F is a MAY feature of the model M, then there can be no
09700	contradiction between F and ⊗4any⊗* features of the scene S.
09800		When a BEING is said to do or recognize or know something, as
09900	in the preceding and following paragraphs, what is actually meant  is
10000	that  one or more of its parts specificly encode that knowledge.  All
10100	the parts of the hundred BEINGs in PUP6 were coded by  hand,  not  by
10200	each  other.  They then can encode other BEINGs, interacting only via
10300	the dialogue.
10400		The  IS_OF_TYPE  BEING  recognizes  that it must work hard to
10500	replace each of the two case tests, unless  M_FEATURES  is  organized
10600	permanently  into  three  parts (thus permitting the complex function
10700	"IS_OF_TYPE" to be replaced by the simple one "MEMBER" in  the  above
10800	piece of code). The STRUCTURE_INDUCING BEING will take over, to probe
10900	the permissability and the difficulty of such a constraint.  It finds
11000	nothing  about  this  tripartite  structuring  which could damage any
11100	earlier synthesized code, and asks the  user's  blessing.  Notes  are
11200	added  to  the list of coding warnings, stating that any reference to
11300	the entire list of M_FEATURES must be replaced by  either  APPEND  of
11400	the  three  new lists, or else by three separate statements. GET_NAME
11500	is indirectly called, and he has the user name the three new sets  of
11600	features; say he responds by calling them MUSTNOT, MUST, and MAY. The
11700	system would at this point say to draw an arrow on its graph of code,
11800	from the function call (IMPOSS F S_FEATURES) to the new block of code:
11900	.B
12000	
12100	  (COND ( (MEMBER        F   MUSTNOT_PART_OF_M)
12200		  (MEMBER        F   S_FEATURES))
12300	        ( (MEMBER        F   MUST_PART_OF_M)
12400		  (NOT (MEMBER   F   S_FEATURES))
12500	        (  T (COMMENT THIS "T" REPLACES "MEMBER F MAY_PART_OF_M")
12600		   NIL))
12700	.E
12800		This is now the META:CODE part of the new BEING called IMPOSS.
12900	Most of the other parts are taken from its generalization, namely
13000	CONTRADICTS. During the course of writing this piece, however, some
13100	of these parts would be slightly changed. For example, its reason
13200	for existing would be strengthened when the simple MEMBER function
13300	calls replaced the slow IS_OF_TYPE  BEING calls.
13400	Here is the actual transcript of this part of the dialogue; it may also
13500	be seen (with the names slightly changed) in the appendix, on
13600	pages  A5.10  to  A5.12.  
13700	
13800	.NOFILL
13900	MOVE CURSOR TO  IMPOSS TYPE OF   CONTRADICTS
14000	
14100	SORRY TO BOTHER YOU, BUT I CAN NO LONGER DEFER THIS SOMEOF DECISION
14200	    (PROBABILITY=1:CONTRADICTION PROBABILITY=0:CONTRADICTION 
14300		PROBABILITY>0&<1:CONTRADICTION)
14400	SINCE THE DECISION IS SOME:OF, TYPE ANY ORDERED SUBSET OF:
14500	  (A .... PROBABILITY=1:CONTRADICTION)
14600	  (B .... PROBABILITY=0:CONTRADICTION)
14700	  (C .... PROBABILITY>0&<1:CONTRADICTION)
14800	
14900	<discussion of the ramifications of each of these types of contradiction>
15000	
15100	USER: ⊗4(A B C)⊗*
15200	
15300	(I RECOMMEND THAT POSSIBLE:NAME:OF:CLASS:RELNS BE STRUCTURED INTO (AT
15400	    LEAST ALONG ONE DIMENSION) THESE 3 PIECES:
15500	(PROBABILITY=1:CONTRADICTION:PART:OF:POSSIBLE:NAME:OF:CLASS:RELNS 
15600	 PROBABILITY=0:CONTRADICTION:PART:OF:POSSIBLE:NAME:OF:CLASS:RELNS 
15700	 PROBABILITY>0&<1:CONTRADICTION:PART:OF:POSSIBLE:NAME:OF:CLASS:RELNS).
15800	PLEASE TYPE BACK YES, NO, OR UNSURE.)
15900	
16000	USER: ⊗4YES⊗*
16100	
16200	PUP WANTS USER TO TYPE IN NAME FOR SPECIALIZED VERSION OF 
16300	  ( PROBABILITY:1:CONTRADICTION:PART:OF:POSSIBLE:NAME:OF:CLASS:RELNS)
16400	USER: ⊗4YES:RELNS⊗*
16500	 .
16600	 .
16700	 .
16800	DRAW A LINE FROM THE FUNCTION CALL  (IMPOSS RELATION ELEMENT:RELNS)
16900	          OF THE FUNCTION IMPOSS TO THIS NEW PIECE OF CODE, WHICH
17000	    IS ITS BODY:
17100	
17200	(IMPOSS
17300	  (LAMBDA (ARG1 ARG2)
17400	    (COMMENT IN ALL CALLS TO DATE, ARG1 IS INSTANTIATED AS RELATION
17500	      AND ARG2 IS INSTANTIATED AS ELEMENT:RELNS)
17600	    (COND
17700	      ((MEMBER ARG1 YES:RELNS)
17800		(COMMENT ARG1 OCCURS WITH PROBABILITY 1, SO IT HAD BETTER BE
17900	                         IN ARG2, THE RELEVANT PIECE OF THE WORLD)
18000		(NOT (MEMBER ARG1 ARG2))))
18100	      ((MEMBER ARG1 NO:RELNS)
18200		(COMMENT SINCE ARG1 SHOULD NEVER OCCUR, WE HAVE A 
18300	        	CONTRADICTION IF IT IS A MEMBER OF ARG2)
18400		(MEMBER ARG1 ARG2)))
18500	      (T (COMMENT WE MAY OR MAY NOT HAVE ARG1 IN ARG2; EITHER
18600			       CASE IS ALLOWABLE; SO WE
18700	                       NEVER HAVE A CONTRADICTION)
18800		NIL))))
18900	
19000	IMPOSS  has now been redefined as a BEING.
19100	
19200	(IN ALL CODE GENERATED,
19300	    ALL OCCURRENCES OF POSSIBLE:NAME:OF:CLASS:RELNS HAVE BEEN REPLACED
19400	    BY   (APPEND YES:RELNS NO:RELNS MAYBE:RELNS))
19500	
19600	.FILL
19700	Notice that only a few messages have passed
19800	from user to PUP6 during all this processing.  The user has the  feeling
19900	of  merely  directing, constraining, and watching the activities of a
20000	busy programmer.   Unfortunately, "the user" is  not  generic;  there
20100	was  only one successful user. As was mentioned earlier, PUP6 insists
20200	on doing structured programming,  so  its  traces  are  superficially
20300	similar to  macro  expansion. Despite this concentration on planning,
20400	no BEINGs system 
20500	should mistakenly halt so long as any details remain.
     

00100	.NEXT PAGE
00200	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},REALITY:  RESULTS)
00300	⊗27. REALITY:  RESULTS⊗*
00400		The  character of the dialogue (described in Section 6 and in
00500	Appendix 5) is, of course, one important measure of the  intelligence
00600	of  an  AP  system.   One which asked "What is the first instruction?
00700	What is the second...?" would be universal but worse than useless. In
00800	this  section  are  some  proposed  questions  one  should  ask  when
00900	confronted by a new AP system and some measures of performance of any
01000	AP system which generates code heuristically from a dialogue.
01100	The answers pertaining to PUP6 are parenthesized after each question.
01200	Only capsules are given; fuller answers are located elsewhere.
01300		The questions break into two categories. First, one wants  to
01400	know  what the system does.  Most important, does it write a program?
01500	(yes.)
01600	If  so,  how  complex  is  that  task,  and  what  is   the   program
01700	specification  like? (a concept formation program, several pages long,
01800	from one specific protocol dialogue).  
01900	How precise must the user be:    may he err (no),
02000	forget (no), change his mind? (yes, in limited cases.) 
02100	How detailed must his  dialogue  be? (by construction, just about as
02200	detailed as if he were talking to a CS grad student programmer.) How
02300	closely  does  the  dialogue determine the details of the final code?
02400	(some inferences are made, and several representational choices, but
02500	much of the 
02600	final code is clearly determined by the precise user responses.)
02700	How does the user know where he is during the dialogue? (simulated cursors
02800	pointing to a graph representing synthesized code.)
02900		Quite  seriously, an important question is whether the system
03000	writes a second program. (yes.)  
03100	If so, how does it relate to the first  one
03200	synthesized? (both are inductive inference LISP programs.) 
03300	How much of the AP system is actually used in writing
03400	⊗4both⊗* programs? (49 BEINGs out of 79.) 
03500	One should ask what the full range of programs is
03600	which  the system has successfully synthesized. (the concept former, the
03700	grammatical inferrer, and the simple information manipulation system.)
03800	The dual questions to
03900	these inquire whether a program may be generated by several different
04000	dialogues (theoretically, but not practically),  
04100	and  what  the  range  of variability is. (theoretically large, but
04200	practically quite limited.) Similarly, what
04300	about the target language: is it a parameter? (no, always the same.) 
04400	how does it  relate  to
04500	the language the system is written in? (both written as BEINGs in 
04600	INTERLISP.)
04700		Does the system modify as well as write code? (yes, but not
04800	as its major mechanism.)   If so,  can
04900	it  modify  anybody's,  or only those programs it has written itself?
05000	(only its own, and only in simple ways.)
05100	What is its "style" of programming? (many supplementary comments,
05200	fairly clean structured programs only.) 
05300	One also wishes to know the  size
05400	of  the tool as well as the size of the job: How does the system size
05500	compare to target program size? (one order of magnitude larger.)
05600		Efficiency considerations are often the crucial
05700	pragmatic ones. Economics and current hardware restrict the amount of
05800	computation  which  may be done in toto; the expected lifetime of the
05900	universe restricts us from using the  most  elegant  algorithms;  and
06000	human  patience  restricts the interaction delay time (to a minute or
06100	two of real time). One must therefore  ask  things  like
06200	how  much  time  and  space  it  requires,  how long a delay there is
06300	between user inputs, etc. (one CPU hour, 100K, under a CPU minute 
06400	between responses.)
06500		The  second  class of questions concerns the theoretical side
06600	of the AP system.  What new ideas is it meant to experiment with? 
06700	(this is the subject of most of the preceding text; see esp. section 
06800	3.) How
06900	do each of these ideas fare? (many surprises; this is the subject of
07000	most of the remainder of this paper; see esp. section
07100	8.) Does it write its code in the right way?
07200	(it asks the right questions of  the  user  at  just  the  proper
07300	times with respect to the original protocol.)
07400	How extendable is it: how difficult is it to add new pieces
07500	of knowledge and to modify old ones? (theoretically easy, practically it
07600	requires familiarity with the system.)  Could  it  write  programs  in
07700	various fields (probably), in various styles (possibly), in various sizes?
07800	(the three target programs differ < one order of magnitude.)
07900		How is knowledge  represented  internally? (BEINGs, assertions,
08000	demons.)   Is  any  of  it
08100	duplicated? (not above the LISP language level.) 
08200	If so, what and why? Why doesn't this system solve the AP
08300	problem? (it was mistakenly thought that the problems of dialogue were not
08400	central to "the AP problem.")
08500		Detailed answers  to most of the these questions are scattered
08600	throughout the earlier sections of this paper.  Below are its answers
08700	in detail to the remaining questions.  
08800		Although BEINGs can theoretically handle
08900	user errors, PUP6 was set up expecting that the user would never  err
09000	or  forget.  He could, after the program was finished, try it out and
09100	describe how he wished it changed. Occasionally, PUP6  actually  make
09200	the  right modifications. For example, INF,
09300	the simple data storage and retrieval on keys
09400	system which was written, was supposed to store and retrieve airline
09500	reservations.   After the synthesis is finished, the user tries
09600	out the program and finds that he is unable to delete more  than  one
09700	reservation  with  any  single  command. He complains about this, and
09800	PUP6 modifies the program so that he may specify a pattern,  and  all
09900	reservations  matching  that  pattern  will  be  purged.   While 
10000	assumptions of absolute 
10100	user reliability are reasonable for  little  programs,
10200	they  break  down  when the tasks reach the size of tens of pages and
10300	hours.
10400		Let  us  briefly  describe  GI  and  INF, the second and
10500	third programs PUP6 synthesized.   GI  is  a  simple
10600	grammatical inference program. It builds up a set a plausible  rules,
10700	rather  than  enumerating  through  the space of all grammars. Yet it
10800	lacks most of the "tricks" of  the  best  g.i.  programs.   The  user
10900	repeatedly specifies a string, labelled LEGAL, ILLEGAL, or ??. In the
11000	latter case, GI must print out its guess and accept the correct label
11100	from  the  user.   In  all  three  cases,  it  must update its set of
11200	plausible rules to be at  least  consistent  with  all  positive  and
11300	negative  instances  observed. In some versions of GI the user coaxes
11400	PUP6 to generate, a parse tree may be maintained  and  inspected;  in
11500	other versions, just a list of the rules used during a parse is kept.
11600		INF is a data-retrieval-on-keys system.
11700	The user repeatedly types
11800	in a request to insert, delete, or inspect a  record  (e.g.,  INSERT:
11900	PASSENGER  Jones  FLIGHT  741  FROM SFO TO LAX CARRIER TWA LEAVE 7:15
12000	ARRIVE 8:00).  Any unspecified fields are treated  as  dont't  cares;
12100	thus the request is matched against entries in the data base.
12200		The table below shows how each type of knowledge was used  in
12300	writing the three target programs.  All numbers refer to BEINGs.
12400	
12500	.BEGIN
12600	.GROUP
12700	.NOFILL
12800	.FONT 7 "FIX20"
12900	.SELECT 7
13000	.BREAK
13100	
13200	.ONCE CENTER
13300	                ⊗4U S E D   I N   S Y N T H E S I Z I N G⊗*         
13400	
13500	TYPE OF        CF    CF    CF    CF     GI    INF     not     Crea    Crea    Crea    Total          
13600	KNOWLEDGE      GI    GI   INF   only   only   only    used    -ted    -ted    -ted    BEINGs
13700	              INF   only   only                       ever    in CF   in GI   in INF
13800	
13900	Programming    39     7     5     5     3      1       14       52      27      21      174
14000	Domain          0     3     0     9     8      1        5        4      10       3       43
14100	Total          39    10     5    14    11      2       19       56      37      24      217
14200	.END
14300	
14400	The high percentage of programming BEINGs  which  were  used  in  all
14500	three  dialogues  is exciting.  The three domain-specific BEINGs used
14600	in both CF and GI  sessions  indicate  that  they  may  be  Inductive
14700	Inference  domain specific.  They aren't used in INF, which is not an
14800	inductive inference task. All three deal with partitioning a domain.
14900		A  specialization of a general programming BEING is listed as
15000	a programming BEING still  (in  the  CREATED  columns  of  the  above
15100	table.)  This  is  because  it remains sufficiently independent to be
15200	used in many ways, conceivably in many different programs.
15300		The  style  of  the synthesized programs is constrained since
15400	all code must be BEINGs. At a lower level,  there  are  many  trivial
15500	inefficiencies which are passed through a BEING which is to optimize
15600	LISP programs out of context, at a low level.  This BEING is
15700	vacuous now, but may soon contain a LISP optimizer being  written  by
15800	A.  Cohn of the SAIL AP group. Low level efficiency was intentionally
15900	ignored to expedite work  on  PUP6.   Nevertheless,  the  final  code
16000	produced  runs  in  about  the  same  time as the hand-coded versions
16100	(e.g., a few seconds per scene for CF).  It is several times as long,
16200	though,  since  it  must  be able to answer questions about what it's
16300	doing as it runs.  The  protocol  version  lacked  this  ability,  of
16400	course.
16500		One  crude  measure  of  concentration  of intelligence is to
16600	compare the system  and  target  code  lengths.  Ephemeral  numerical
16700	efficiency  data  such  as  this follows. PUP6 is 200 pages long when
16800	PRETTY-PRINTED, and has synthesized three programs, 7, 20, and 30
16900	pages long (1, 4, and 6 pages, when coded by hand.)
17000		A  brute  force  AP  system  would  require  a  time  roughly
17100	exponential  in  target  length, so log(time)/target_length (measured
17200	over several different programs and over several AP  systems)  is  an
17300	indicator  of  the  intelligence of an AP system.  For a good system,
17400	this number should (i) be small absolutely,  and,  more  importantly,
17500	(ii)  decrease  significantly as the target program length increases.
17600	For a ⊗4very⊗* good program writer, the  quantity  time/target_length
17700	stays   almost  constant.   This  is  not  quite  achieved  by  human
17800	programmers known to the author.
17900		Two important factors are omitted when simply comparing system
18000	and target lengths. First, one might improve any such measure by simply
18100	decreasing the size of a given system. This is wrong, since, e.g., 
18200	removing all the comments from a program shouldn't increase its
18300	intelligence!  Secondly, the total amount of distinct target programs
18400	should be considered. Compilers turn out programs small compared to
18500	themselves, but are valuable because of the vast variety of such programs
18600	they can put together.
18700	This factor reflects how much of the "guts" of the system can be used in
18800	writing many programs.
18900		PUP6  takes  60  cpu minutes to produce CF. During this time,
19000	300000 characters get typed out to the user, who  reponds  with  about
19100	4000  himself. The dialogue lengths are best specified in characters,
19200	since often the user will supply simply a number or  a  letter  or  a
19300	YES/NO  reply.   Dividing  these by a hundred, one can relate them to
19400	target and system lengths in lines. Even  the  character  counts  are
19500	very  rough,  because  the  format  of  the AP dialogue can easily be
19600	varied by a couple orders of magnitude.  The mean wait time  (between
19700	the user's input and the next machine output) is several seconds. The
19800	longest delay  between  successive  user  inputs  is  1  CPU  minute.
19900	Unfortunately,  PUP6  requires 100K to run in, which (with INTERLISP)
20000	exhausts the virtual memory of the current hardware being  used.  One
20100	would lose vast amounts of time by using intermediate storage devices
20200	or by running consecutive communicating jobs. Efficient use of multiple
20300	processors and of extended core storage could be made.
20400		INF  was  one fifth the size of CF, and took about a seventh
20500	as long to generate. The dialogue was shorter by a factor of three.
20600		Most  of  the  theoretical questions are answered by the very
20700	design of the system. Its ideational foundation has  been  discussed.
20800	When  the  user  sticks close to the original protocol, PUP6 asks the
20900	right questions at the right times because of its genesis  from  that
21000	annotated  protocol.   The  second  and third programs were attempted
21100	only to test its flexibility, and the results were mixed.
21200		First  the bright side. The increment to PUP6 to enable it to
21300	write the GI and the INF programs is encouragingly small. Almost  all
21400	the  programming-knowledge BEINGs are called in writing more than one
21500	of the programs. It is now clear  that  very  domain-specific  BEINGs
21600	were in control at the early, high levels. Later, more general BEINGs
21700	took over, followed by pure programming BEINGs.  The middle  category
21800	would  include II BEINGs like PARTITION_A_DOMAIN.  
21900		Regrettably, incrementing the system with new domain-specific
22000	BEINGs is not feasable for the average user.  To add a BEING, he must
22100	specify  all  of  its relevant parts. Each is inputted either as LISP
22200	code, as an English sentence PUP6  is  capable  of  interpreting,  an
22300	English  sentence  PUP6  is  just  supposed  to  remember as a canned
22400	response, or by pointing to a part of an existing  BEING  and  saying
22500	"like  that  one,  except  ...", where the preceding ellipsis must be
22600	very simple.  The interactions between the BEINGs, and  the  existing
22700	set of BEINGs, need not be fully understood; but the set of allowable
22800	assertion templates, the mechanisms by which each part is  used,  the
22900	special  data types involved (VECTOR, TUPLE), and the precise actions
23000	of each new part ⊗4must⊗* be known in order to safely  inject  a  new
23100	BEING.
23200	This may be a result of the small amount of knowledge in PUP6. One would
23300	hope that a BEINGs system which was expert in a domain could assist the
23400	user in adding new domain-specific BEINGs, in the same way that the
23500	BEINGs which make up the target code are synthesized, through dialogue.
     

00100	.NEXT PAGE
00200	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},THEORY:  CONCLUSIONS)
00300	⊗28. THEORY:  CONCLUSIONS⊗*
00400		The strengths and weaknesses of both BEINGs and PUP6 are
00500	reviewed.
00600	This experiment has helped clarify some 
00700	of the potential problems facing
00800	future AP work.
00900		While the number of  BEING-parts  is
01000	unimportant,  its magnitude (a few tens) may have significance to AP.
01100	The fact that is isn't ~1 may help explain the difficulty with predicate
01200	calculus representations; the fact that it isn't ~1000 
01300	may mean that the AP
01400	problem is tractible.
01500		Some of the ideas discussed at the  beginning  of  the  paper
01600	have proven themselves to be useful in getting PUP6 to work. 
01700	Little programs
01800	can indeed be treated as if their essence  is  nothing  more  than  a
01900	collection  of  answers.   The  gain  from  standardization  is 
02000	conceptually easy
02100	addition of pieces to the system; one "merely" adds new BEINGs to the
02200	community. Their interactions with all the existing BEINGs needn't be
02300	known in advance. As was discussed in the previous section, the 
02400	actual addition is beyond the power of the untrained user.
02500		Indications   are  that  one  ⊗4can⊗*  locate  relevant
02600	information by organizing the knowledge in a pool,  with  each  piece
02700	(i)  responsible  for  recognizing  when  it  is  relevant  and  (ii)
02800	indicating new relevant information indirectly  via  nondeterministic
02900	pattern-directed  retrievals  and  assertions.  Notice that this puts
03000	all control structure into the hands  of  the  BEINGs;  there  is  no
03100	central  monitor  in  PUP6.   A  BEING's answers may at various times
03200	indicate that it should be chosen to be in control, and it will  then
03300	take  over.   Notice  also  that this relevancy problem is central to
03400	program maintenance as well as synthesis. It is not clear whether 
03500	or not this really beats the exponential growth of this problem.
03600		The  fact  that target code is in the format of BEINGs limits
03700	the size of the target programs (≥ one page) and their efficiency  (a
03800	BEING-call  is a very slow and intricate process) and of course their
03900	style. The most startling result -- which should have been forseen --
04000	was that "intelligent" target code is synthesized. This was mentioned
04100	casually in the IDEAS section, but its importance is clear: the  code
04200	is  self-commenting  in the strong sense that the code can answer any
04300	(of our set of 29) questions about itself.  Those which make sense at
04400	compile-time  can  be  asked  then;  those  which  make  sense during
04500	execution may be asked then.  For example, CF begins  running.  After
04600	several  scenes have been processed, CF is waiting for a new one.  If
04700	the user interrupts  and  asks  what  it  is  doing,  CF  will  reply
04800	"awaiting user input of a brand new scene." One can ask why, how, who
04900	will be affected, and so on, interrupt as frequently  as  desired  --
05000	even  after  each  BEING  transfers control. The actual questions and
05100	responses are not very impressive, but they are at least at the  same
05200	level as those which can be gotten from PUP6 itself as it runs.
05300		The set of questions the user was expected to want to ask the
05400	system  is  similar  to the questions one BEING wants to ask another.
05500	So when the "nice" user interrupts, his questions are almost always a
05600	simple  retrieval  from a property list (a GETP or a composition like
05700	EVALπ.GETP). When the average  user  interrupts,  his  questions  are
05800	often unintelligible to PUP6.
05900		Meaningful use of comments proved helpful. As an example, the
06000	comment at the end of the main outer loop was "COMMENT, INFINITE LOOP
06100	IN THIS PROG" (see page A5.10) for most of the session. Near the  end
06200	of  the  session,  the  CLARIFY_IMPROBABLE_SITUATION BEING recognizes
06300	this as a warning, works on introducing a breakaway  test,  and  then
06400	replaces  the  comment by one indicating that no infinite loop exists
06500	there anymore (see  page  A4.4).   The  advantage  to  embedding  our
06600	insertions in the code this way is that, at any stage, the user could
06700	inspect the code and get something meaningful  out  of  the  comments
06800	which were present.
06900		The  careful  bookkeeping   actually   did   eliminate   some
07000	carelessness  errors, though it had no effect on user errors or later
07100	program maintenance  directives.  These  latter  processes  are  less
07200	ill-defined  than  blind debugging, and in fact are about the same as
07300	programming itself [Dijkstra].  The deferral  of  decisions  has  the
07400	nice corollary of reducing (though not minimizing) communication with
07500	the slow user channel.
07600		Synthesizing a new, 
07700	clean target program  probably  would  require
07800	adding  a  few domain-independent BEINGs and several domain-specific
07900	BEINGs, and generalizing several parts of  several  existing  BEINGs.
08000	Since  the  dialogues  for  GI  and INF were not studied before-hand,
08100	their acceptability  would  have  demonstrated  the  success  of  the
08200	system.  Most of the existing BEINGs were used in generating these
08300	new programs, but a few new BEINGs had to be added. Equally
08400	discouraging, the dialogue to write INF is too long and detailed
08500	for the task at hand.  It also  seems  that  the  front  end  is  too
08600	brittle  to  allow  anyone  unfamiliar with the system to easily work
08700	with it.
08800		The need for flexible communication stems  only
08900	partially from inter-user  differences.   A  serious  and  unexpected
09000	source  of  conflict  here  is the amount of inference the user wants
09100	done.  This level is relatively subjective, and may fluctuate rapidly
09200	even  with  one  user  writing one program. Perhaps there should be a
09300	dial he can set. At one extreme, the system would  ask  the  user  to
09400	verify  even  the  most  trivial  inductions.  At  the  other extreme
09500	setting, the system would probably write  the  target  program  after
09600	just a few brief user inputs. The user would then try out one program
09700	after another, interjecting just one or two comments each time, after
09800	which  the  system would come up with the next version.  This program
09900	modification mode seems appropriate for someone ignorant of LISP, who
10000	nevertheless has the I/O behavior of his target clearly in mind.
10100		Some of the BEING parts  proved  embarrassingly  unnecessary.
10200	The  CO-REQUISITES  part was never used.  The only activity which had
10300	to be done concurrently was demon activation. The AFFECTS part was of
10400	interest  to  the  user  occasionally,  but  never to any BEING.  The
10500	EFFECTS part originally had a twin, describing what would  happen  if
10600	each  BEING  were  ⊗4not⊗*  called right now.  In each case, this was
10700	merely a trivial restatement of the frame problem.  So,  like  STRIPS
10800	[Fikes],  PUP6  ignores  the  frame  problem:     all changes must be
10900	explicit.
11000		Much  of PUP6's comments are boring and unnecessary; this was
11100	felt to be an engineering problem which would be ignored in all but a
11200	"marketable"  AP system. This view was probably incorrect. One of the
11300	most severe AP problems is having  the  system  inform  the  user  of
11400	precisely  what  he should know -- no more nor less.  This requires a
11500	sophisticated  user  model  cleverly  interfaced   to   the   current
11600	programming task.
11700		Another problem with large, long dialogues is user  error.  A
11800	human  has  great  difficulty keeping "on top" of everything.  He may
11900	get lost, forget, change his  mind,  or  misunderstand.  Again,  this
12000	problem  was originally considered ignorable, but has shown itself to
12100	be  a  limiting  practical  factor  in  wide  accessability.  It  was
12200	necessary  to  create  a  forgetful-user  demon  to prevent anaphoric
12300	reference to something which, though uniquely determined, hadn't been
12400	mentioned within the past several seconds.
12500	Related to this is the problem of keeping
12600	the user informed of where he is. PUP6 simulated a continuous display
12700	of  the graph of the current partial program, augmented by static and
12800	dynamic cursors. This  use  of  dynamic  and  textual  indices  seems
12900	insufficient.   The  user was still often confused, wishing a section
13000	referred to not by pointing but rather by a brief, meaningful (to him
13100	only!)  phrase.   This may also be one of the major AP problems which
13200	must be studied further.
13300		These  worries  about large dialogues arise because future AP
13400	systems are viewed as tools for writing programs which humans  simply
13500	cannot  manage  currently:      viable natural language systems, huge
13600	operating systems, better AP systems.
13700		McCune  calls attention to an argument against ever needing a
13800	system whose target programs will be longer and more complex than the
13900	system  itself.  First,  empirically, optimizing compilers are viable
14000	and yet they dwarf almost all the code they generate.  Second, as the
14100	complexity  of the transformation increases, the length of a compiler
14200	increases rapidly.  For a truly intelligent AP system, one  might  be
14300	willing  to  tolerate a program several times as large as anything it
14400	could produce.
14500		An  argument  exists  to  counter this one.  First, one might
14600	object to drawing  an  analogy  from  compilers;  many  entities  are
14700	capable  of  producing  things  more  sophistocated  than themselves,
14800	larger than themselves, etc. (consider evolution). Second,  it  seems
14900	that there is a manageable body of information which one needs master
15000	to do programming [informal].  Viewed differently, one can
15100	write  programs  as long as he wishes if the program is designed in a
15200	clean way. Thus the size of AP systems will probably
15300	level  off  (albeit  huge
15400	compared  to  existing  programs)  even as the size and complexity of
15500	their generated code continues to increase and,  eventually,  surpass
15600	them.  Finally,  we  must  consider why we want a good AP system:  to
15700	help  us  write  large  programs  easily,  programs  which  might  be
15800	unmanageable  today.   For  this  reason alone, our AP system must be
15900	able to deal with programs larger than itself.
16000		The whole design of BEINGs  is
16100	oriented   toward  this  large-scale  end.  One  cannot  write  tiny,
16200	super-efficient programs using BEINGs, any more  naturally  than  one
16300	can  generate  efficient machine code using a high level language. 
16400	A BEINGs system might simulate this activity, but it would be as
16500	awkward and opaque as if they were asked to simulate volleyball. By
16600	relinquishing  more  and  more  control  to  the  computer   language
16700	environment,  the  programmer  sacrifices specialization of the final
16800	code for ease of  constructing  it  and  for  its  greater  size  and
16900	complexity.
     

00100	.NEXT PAGE
00200	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE})
00300	⊗29. ACKNOWLEDGEMENTS⊗*
00400	
00500		There  are,  of  course,  countless  ideas  embodied  in  any
00600	concrete project.  Sweeping philosophical assumptions are made simply
00700	by deciding to do any type of programming [McCarthy], even moreso with
00800	Automatic Programming. Any
00900	Program-Understanding  Program  should  include the best parts of all
01000	the best old ideas.  PUP6 relies  on  concepts  gleaned  from  Actors
01100	[Hewitt],   Demons   [........],   heterarchy   [.....],   structured
01200	programming [Dijkstra], assertional  data  bases  and  flexible  data
01300	types  [Rulifson], pattern-directed invocation of procedural knowledge
01400	[........], the paradigm of AP by dialogue [Floyd], 
01500	and studies on  program
01600	specification techniques [Green].  Of course this list is incomplete;
01700	sophisticated ideas are captured in the languages themselves:   QLISP
01800	[Reboh],   INTERLISP   [Teitelman],  LISP  [McCarthy2],  and  English
01900	[Anonymous]. To this rich store, one may achieve new  heights  merely
02000	by synergy.
02100		Any success of the BEINGs project, as well as  the  precursor
02200	PUP  programs  [Green]  is due in large measure to the 
02300	creative energy of C.  Cordell  Green.   I  have
02400	also  drawn  upon  discussions  with
02500	D. Barstow, B.  McCune,  D.   Shaw,  E.
02600	Sacerdoti, L.
02700	Steinberg,  and  R.  Waldinger.   The generosity of SRI, in providing
02800	computer time and language consultations, should not go unmentioned.
02900	Also valuable were the critical readings of this paper by R. Davis
03000	and T. Winograd.